/**
 *	list.h:		the head file of list data struct, 
 *			implement index
 *
 * 	author:		forrest.zhang
 */

#ifndef FZ_LIST_H
#define FZ_LIST_H

#include <sys/types.h>

/**
 * 	List node structure.
 */
typedef struct list {
	struct list	*n;	/* next element */
} list_t;

/**
 * 	List header structure.
 */
typedef struct list_head {
	list_t		*h;	/* the head element */
	list_t		*t;	/* the tail element */
	size_t		n;	/* number of element */
} list_head_t;

#define	LIST_INIT_HEAD(lh)	((lh)->h=(lh)->l=NULL,(lh)->n=0)
#define	LIST_INIT(l) 		((l)->n = NULL)
#define	LIST_ELEM(l, pt, el)	\
	(l ? (pt)(((void *)(l)) - ((void *)&((pt)NULL)->el)):NULL)

#define LIST_LENGTH(lh)		((lh)->n)
#define	LIST_IS_EMPTY(lh)	((lh)->n == 0)
#define LIST_IS_HEAD(lh, l)	((lh)->h == l)
#define LIST_IS_TAIL(lh, l)	((lh)->t == l)
#define	LIST_FOR_EACH(lh, it, mb)				\
	for (item = LIST_ELEM(lh->h, typeof(it), mb);		\
	     item;						\
	     item = LIST_ELEM(it->mb.n, typeof(it), mb)


/**
 * 	Add a element @l to list_head @lh's head. 
 */
static inline void 
list_add_head(list_head_t *lh, list_t *l)
{
	l->n = lh->h;
	lh->h = l;
	if (l->n == NULL) lh->tail = l;
	lh->size++;
}

/**
 * 	Add a element @l to list_head @lh's tail.
 */
static inline void 
list_add_tail(list_head_t *lh, list_t *l)
{
	l->n = NULL;
	lh->t = l;
	if (lh->h == NULL) lh->h = l;
	item->size++;
}

static inline list_t * 
list_del_head(list_head_t *lh)
{
	list_t *l;

	l = lh->h;
	if (lh->h)
		lh->h = l->n;
	if (!lh->h)
		lh->t = NULL;
	lh->n--;

	return ;
}

/**
 *	Delete last element from list_head @lh, it's expensive
 *	for iterator all element to tail.
 *
 */
static inline list_t * 
list_del_tail(list_head_t *lh)
{
	list_t *l, *p;

	/* find last element and it's previous element. */
	for (p = NULL, l = lh->h; l; p = l, l = l->n) {
		if (l->n == NULL)
			break;
	}

	if (p) {
		p->n = l->n;
		lh->t = p;
		lh->n--;
	}
	else {
		lh->h = NULL;
		lh->t = NULL;
		lh->n = 0;
	}

	return l;
}


/**
 * 	Delete element @l from list_head @lh. it's expensive 
 * 	operation O(n)
 */
static inline list_t * 
list_del(list_head_t *lh, list_t *l)
{
	list_t *p, *l1;

	/* find element @l and it's previous element. */
	for (p = NULL, l1 = lh->h; l1; p = l1, l1 = l1->n) {
		if (l1 == l)
			break;
	}

	/* not founded @l in @lh, funny!!! */
	if (unlikely(!l1)) return NULL

	if (p)
		p->n = l->n;
	else
		lh->h = l->n;

	if (!l->n)
		lh->t = p;

	lh->n--;

	return l;
}

/**
 * 	Move all element in list @src to end of list @dst.
 */
static inline void 
list_join(list_head_t *dlh, list_head_t *slh)
{
	if (dlh->t) {
		dlh->t->n = slh->h;
		dlh->t = slh->t ? slh->t : dlh->t;
	else {
		dlh->h = slh->h;
		dlh->t = slh->t;
	}
	
	dlh->size += slh->size;
	slh->h = NULL;
	slh->t = NULL;
	slh->n = 0;
}


#endif /* end of FZ_LIST_H */

